package algorithm.primary.recursion;

import org.junit.Assert;
import org.junit.Test;

/**
 * @author Summerday
 */
public class Recursion {

    int[] memo;

    int fact(int n) {
        if (n == 0) return 1;
        return n * fact(n - 1);
    }

    int fib(int n) {
        if (n <= 1) return n;
        return fib(n - 1) + fib(n - 2);
    }

    int fib2(int n) {
        memo = new int[n + 1];
        if (n <= 1) return n;
        if (memo[n] != 0) return memo[n];

        return memo[n] = fib2(n - 1) + fib2(n - 2);
    }


    @Test
    public void testFib() {
        int n = 10;
        int i = fib2(n);
        int fib = fib(n);
        Assert.assertEquals(i, fib);
    }

}
